/**
 * @param {number[]} nums
 * @return {number[][]}
 */

type VisitedType = {
  [key: number]: number;
};
var permute = function (nums:Array<number>) {
  // 缓存数组的长度
  const len = nums.length;
  // 定义数组,保存全排列结果项
  const res: Array<Array<number>> = [];
  // 定义当前排列
  const cur: Array<number> = [];
  // 定义visited避免重复使用同一项
  const visited:Record<number,number> = {};
  // 定义dfs
  const dfs = (nth: any) => {
    // 定义递归的边界,此时坑位已经全部占满
    if (nth == len) {
      res.push(cur.slice());
      return;
    }
    // 检查现在剩余的数字有哪些
    for (let i = 0; i < len; i++) {
      // 如果当前数字没被使用过,则可以理解为这个数字是被剩下的
      if (!visited[nums[i]]) {
        // 将数字推入当前坑位
        cur.push(nums[i]);
        // 标记当前坑位数字已经被使用过
        visited[nums[i]] = 1;
        // 继续下一个坑位,需要指出的是,坑位的数量是固定的,全排列的坑位数量就是数组的长度
        dfs(nth + 1);
        // nums[i]让出当前坑位
        // 个人理解,走到这一步,这个排列的坑位已经全部遍历完毕,此时需要将已经占位的nums[i]弹出,从而可以尝试其他的排列方式
        cur.pop();
        // 下掉“已用过”标识
        visited[nums[i]] = 0;
      }
    }
  };
  dfs(0);
  return res;
};

console.log(permute([1, 2, 3]));
